'''
Created on May 19, 2011

@author: anupams
'''
from com.anupam.common.utils import Utils

class TreeNode(object):
  """Class describing a tree node """
  def __init__(self, num=None):
    self.left = None
    self.right = None
    self.value = num 

### COMMON TREE OPERATIONS
class TreeOperations(object):

  def insertNode(self,treeRoot, value):
    """Inserts a node into the tree"""
    temp = None
    currentPointer = treeRoot
  
    while currentPointer:
      temp = currentPointer
      if value > currentPointer.value:
        currentPointer = currentPointer.right
      elif value <= temp.value:
        currentPointer = currentPointer.left
  
    if not temp:
      treeRoot = TreeNode(value)
      return treeRoot
    elif value > temp.value:
      temp.right = TreeNode(value)
    elif value <= temp.value:
      temp.left = TreeNode(value)
  
  def inorderTraversal(self,treeRoot, container):
    """Inorder traversal of the tree i.e sorted starting from lowest value"""
    if treeRoot:
      self.inorderTraversal(treeRoot.left, container)
      container.append(str(treeRoot.value) + ', ')
      self.inorderTraversal(treeRoot.right, container)
  
  
  def treeSearch(self, treeRoot,x):
    """Searches a particular number in the tree."""
  
    while treeRoot:
      if x == treeRoot.value:
        return True
      elif x > treeRoot.value:
        treeRoot = treeRoot.right
      elif x < treeRoot.value:
        treeRoot = treeRoot.left
    return False
  
  def treeMax(self, treeRoot):
    """Finds the largest element in the tree."""
  
    parent = None
    while treeRoot:
      parent = treeRoot
      treeRoot = treeRoot.right
    return parent.value
  
  def treeMin(self, treeRoot):
    """Finds the smallest element in the tree."""
  
    parent = None
    while treeRoot:
      parent = treeRoot
      treeRoot = treeRoot.left
    return parent.value
  
  
  def generateTree(self, count=10, customNumbers = None):
    """Generates a tree of random size."""
    obj = Utils()
  
    #Check to generate tree using numbers passed as list in the arguments.
    if not customNumbers:
      obj.generateNumbers(count)
      #obj.numbers = [902, 848, 38, 19, 12, 320, 658, 538, 881, 27]
    else:
      obj.numbers = customNumbers
  
    #Set the tree root.
    treeRoot= TreeNode(obj.numbers[0])
  
    for i in range(1, len(obj.numbers)):
      self.insertNode(treeRoot , obj.numbers[i])
    return (treeRoot,obj.numbers)

if __name__ == '__main__':
  treeOPerations = TreeOperations()
  treeRoot,numbers = treeOPerations.generateTree()
  inOrderTraversed = []
  treeOPerations.inorderTraversal(treeRoot,inOrderTraversed)
  print ''.join(inOrderTraversed)

  for i in range(len(numbers)):
    out = treeOPerations.treeSearch(treeRoot,numbers[i])
    if out == True:
      print "Found %s " % (numbers[i])
    else:
      print "Not found %s" % (numbers[i])

  print treeOPerations.treeMax(treeRoot)
  print treeOPerations.treeMin(treeRoot)
